package algotithm.leetcode.bytedance.test53;

/**
 * @author zhouyanxiang
 * @Date 2021-03-2021/3/2-22:46
 * @URL https://leetcode-cn.com/problems/maximum-subarray/
 * @Title 53. 最大子序和
 */
public class Solution {

    public static void main(String[] args) {
        int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
        Solution solution = new Solution();
        int subArray = solution.maxSubArray(nums);
        System.out.println(subArray);
    }

    public int maxSubArray(int[] nums) {
        int res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            nums[i] += Math.max(nums[i-1],0);
            res = Math.max(res,nums[i]);
        }
        return res;
    }
}
